package com.cet.qz.unit01.chapter1_3;

/**
 * @program: algorithm
 * @description: 链表反转
 * @author: 陈恩涛
 * @create: 2021-04-17 23:05
 **/
public class Qz1_3_30 {

    private static class Node {
        private int item;
        private Node next;
    }

    /**
     *方法描述： 非递归实现
     *
     * @param x
     * @return com.cet.qz.unit01.chapter1_3.Qz1_3_30.Node
     * @author chenentao
     * @date 2021/4/18 22:25
     */
    public static Node reverse(Node x) {
        Node first = x;
        Node reverse = null;
        while (first != null) {
            //其中first始终指向剩余链表节点的头结点，second指向first.next,reverse指向结果链表的头结点
            Node second = first.next;
            first.next = reverse;
            reverse = first;
            first = second;
        }
        return reverse;
    }

    /**
     *方法描述： 递归实现
     *
     * @param first
     * @return com.cet.qz.unit01.chapter1_3.Qz1_3_30.Node
     * @author chenentao
     * @date 2021/4/18 22:26
     */
    public static Node reverse2(Node first) {
        if (first == null) {
            return null;
        }
        if (first.next == null) {
            return first;
        }
        Node second = first.next;
        //这里rest为反转后结果链表的首节点
        Node rest = reverse2(second);
        second.next = first;
        first.next = null;
        return rest;
    }

    private static void printLink(Node node) {
        Node tmp = node;
        while (tmp != null) {
            System.out.println(tmp.item);
            tmp = tmp.next;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node();
        node1.item = 1;
        Node node2 = new Node();
        node2.item = 2;
        Node node3 = new Node();
        node3.item = 3;
        Node node4 = new Node();
        node4.item = 4;
        Node node5 = new Node();
        node5.item = 5;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        Node reverse = reverse(node1);
        printLink(reverse);
    }
}
